跳到主要内容

LCR 092.将字符串翻转到单调递增

· 阅读需 3 分钟

1、题干​

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使s 单调递增 的最小翻转次数。

 

示例 1：

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

 

提示：

  • 1 <= s.length <= 20000
  • s 中只包含字符 '0' 和 '1'

 

注意：本题与主站 926 题相同： https://leetcode-cn.com/problems/flip-string-to-monotone-increasing/

2、解题思路​

字符串中的 10 打乱了递增顺序，要保证递增性只需要将其替换成 00、01、11 中任意一种，至于替换成哪一种不重要，因为总有一个合适的，重要的是每出现1个 10 翻转次数需要加 1。

因此要求最小翻转次数，只需要循环地把所有 10 全部剔除，并累加翻转次数即可


3、代码​

var minFlipsMonoIncr = function (s) {
    let c = 0;
    while (s.indexOf('10') > -1) s = s.replace(/10/g, () => (c++, ''));
    return c;
};

4、执行结果​

image.png